Матч 334, Закодированная сумма (EncodedSum)

Дивизион 1, Уровень 1

Имеется массив строк numbers, каждый элемент которого представляет собой натуральное число. Только вместо цифр строки содержат буквы от ‘A’ до ‘J’. Каждая буква обозначает одну цифру, а каждая цифра кодируется только одной буквой. Ни одно число не начинается нулем. В задаче требуется найти наибольшее возможное значение суммы всех чисел.

Класс: EncodedSum

Метод: long long maximumSum(vector<string> numbers)

Ограничения: numbers содержит от 1 до 50 элементов, каждый из которых содержит от 1 до 12 букв от ‘A’ до ‘J’. Существует хотя бы одна буква от ‘A’ до ‘J’, которая не является первой ни в одной из строк.

Вход. Массив строк numbers, содержащий набор закодированных чисел.

Выход. Наибольшее возможное значение суммы всех чисел.

Пример входа

numbers

{"ABC", "BCA"}

{"ABCDEFGHIJ"}

{"GHJIDDD", "AHHCCCA", "IIJCEJ",

"F", "HDBIGFJAAJ"}

Пример выхода

1875

9876543210

9888114550

РЕШЕНИЕ

жадный алгоритм

Элементы массива numbers содержат 10 допустимых букв: от ‘A’ до ‘J’. Запишем каждое число в десятичной системе счисления и просуммируем коэффициенты при одинаковых буквах. Например, для первого теста ABC = 100*A + 10*B + C, BCA = 100*B + 10*C + A. Сумма коэффициентов при букве ‘A’ равна 101, при ‘B’ – 110, при ‘C’ – 11. Массив m содержит эти данные в виде пар: <коэффициент, буква>.

Поскольку нам следует максимизировать полученную сумму, то букве с наибольшим коэффициентом должна соответствовать наибольшая цифра, то есть 9. Следующему по величине коэффициенту – цифра 8 и так далее. Сортируем элементы массива m по возрастанию коэффициентов. Единственная проблема – если в сумме задействованы все десять цифр (включая ноль), то не всякая буква может принимать значение 0, а только та, которая не встречается первой в словах. В массиве canzero отмечаем буквы, которые могут принимать нулевое значение: canzero[i] = 1, если буква ‘A’ + i может принимать значение 0.

В отсортированном по значениям коэффициентов массиве m ищем первую букву, которая может принимать нулевое значение и переставляем ее на нулевую позицию. Если в сумме задействовано менее 10 букв, но никакая буква нулевого значения принимать не будет. Сортируем ячейки массива m от первой до девятой.

После описанных процедур букве m[i].first приписываем значение i и вычисляем максимально возможное значение искомой суммы, равное

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

vector<pair<long long,char> > m(10);

int canzero[10];

class EncodedSum

{

public:

long long maximumSum(vector<string> numbers)

{

int i, j;

long long pow10, s;

for(i = 0; i < 10; i++)

m[i].first =0, m[i].second = i + 'A',canzero[i] = 1;

for(i = 0; i < numbers.size(); i++)

{

pow10 = 1;

for(j = numbers[i].size() - 1; j >= 0; j--)

{

m[numbers[i][j]-'A'].first += pow10;

pow10 *= 10;

}

canzero[numbers[i][0]-'A'] = 0;

}

sort(m.begin(),m.end());

for(i = 0; !canzero[m[i].second - 'A']; i++);

swap(m[0],m[i]);

sort(m.begin() + 1,m.end());

for(s = i = 0; i < 10; i++)

s += m[i].first * i;

return s;

}

};